public class CC77 {
    public int minDistance (String word1, String word2) {
        int size1 = word1.length();
        int size2 = word2.length();
        int[][] arr = new int[size1 + 1][size2 + 1];
        for (int i = 0; i <= size1; i++) {
            arr[i][0] = i;
        }
        for (int i = 0; i <= size2; i++) {
            arr[0][i] = i;
        }
        for (int i = 1; i <= size1; i++) {
            for (int j = 1; j <= size2; j++) {
                arr[i][j] = Math.min(arr[i - 1][j],arr[i][j - 1]) + 1;
                if(word1.substring(i - 1,i).equals(word2.substring(j - 1,j))) {
                    arr[i][j] = Math.min(arr[i - 1][j - 1],arr[i][j]);
                }else {
                    arr[i][j] = Math.min(arr[i - 1][j - 1] + 1,arr[i][j]);
                }
            }
        }
        return arr[size1][size2];
    }
}
